package BackTrack.Medium;

import java.util.*;

public class LC0046 {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> permutationCollection = new ArrayList<>();
        boolean[] picked = new boolean[nums.length];
        backTrack(null, nums, picked, permutationCollection);
        return permutationCollection;
    }

    private void backTrack(List<Integer> path, int[] nums, boolean[] picked, List<List<Integer>> permutationCollection) {
        if (path == null) path = new ArrayList<>();

        boolean extendFlag = false;
        for (int i = 0; i < nums.length; i++) {
            if (!picked[i]) {
                extendFlag = true;
                path.add(nums[i]);
                picked[i] = true;
                backTrack(path, nums, picked, permutationCollection);
                picked[i] = false;
                path.remove(path.size() - 1);
            }
        }
        if (!extendFlag) { // 不能再向下扩展
            List<Integer> pathClone = new ArrayList<>(path);
            permutationCollection.add(pathClone);
        }
    }
}
